package class04;

import java.util.LinkedList;

public class Code01_SlidingWindowMaxArray {

	/**
	 * 滑动窗口
	 * @param arr
	 * @param w
	 * @return
	 */
	public static int[] getMaxWindow(int[] arr, int w) {
		if (arr == null || w < 1 || arr.length < w) {
			return null;
		}
		LinkedList<Integer> qmax = new LinkedList<Integer>(); // 双端队列存储的是下标   大 -> 小   ！！！ 双端队列的长度不是固定不变的
		int[] res = new int[arr.length - w + 1]; // res存放每一种窗口状态下的最大值
		int index = 0;
		for (int i = 0; i < arr.length; i++) {
			// R 往右动
			while (!qmax.isEmpty() && arr[qmax.peekLast()] <= arr[i]) { // 窗口不为空，并且新加入队列的值 大于 队列最尾部的值
				qmax.pollLast(); // 不断从尾部弹出队列内的值，直至严格保持单调性
			}
			qmax.addLast(i);

			// L右移，因为滑动窗口内元素数量始终为 3 ，所以i每移动一次就有一个元素出了窗口即过期了
			if (qmax.peekFirst() == i - w) { // i-w过期的下标
				qmax.pollFirst();
			}
			// 滑动窗口内最大元素的更新
			if (i >= w - 1) { // 窗口形成了
				res[index++] = arr[qmax.peekFirst()];
			}
		}
		return res;
	}

	// for test
	public static void printArray(int[] arr) {
		for (int i = 0; i != arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
		System.out.println();
	}

	public static void main(String[] args) {
		int[] arr = { 4, 3, 5, 4, 3, 3, 6, 7 };
		int w = 3;
		printArray(getMaxWindow(arr, w));

	}

}
